The evolution of the telecommunications in general and of the packet switching networks in particular is driven by many factors among which two of them worth emphasizing: technologies and applications.
Emerging Technologies
Communication technologies have realized these last years considerable progress with:
the maturing of new transmission media and specially of optical fiber. High speed rates can now be sustained with very low bit error rates. For example, the very important bandwidth provided by optical connections, their low attenuation and their high transmission quality are turned to account as well as for long distance networks as for high rate local networks. PA1 the universal use of digital technologies within private and public telecommunications networks. PA1 Improving Old Applications PA1 Sub-second response times, which are achievable on low cost personal computers, have raised user expectations so that the lengthy wide area networks response times that were acceptable some years ago are today no longer tolerable. The user interface can be bettered, for example, with fast response full screen applications. PA1 Optimizing Communication Networks PA1 There is a need for rationalizing the many disparate networks that major users have. Investments can be optimized by integrating heterogeneous traffics like voice, video, and data over the same transport facilities regardless of protocols. Users want the opportunity to control their networking cost by choosing among the different price/performance options offered by the variety of vendors and carriers and to maximize their ability to take advantage of applications built on top of disparate underlying network technologies. However, the motivation for rationalization this is not only to save money on links but also to provide a better networking service by integrating the many disparate networks into a single coherently managed unit. PA1 Doing New Applications PA1 Emerging applications like graphic, image, video, and multimedia processing are requiring a very large volume of traffic. These new applications that were not feasible (or indeed imaginable) before are now becoming accessible generating an ever-increasing demand on bandwidth. PA1 a very large flexibility to support a wide range of connectivity options, PA1 a very high throughput and a very short packet processing time, PA1 a efficient flow and congestion control. PA1 the flow control for regulating the emitting data rate of the calling subscriber at a rate compatible with what the receiver can absorb. PA1 the load regulation for globally limiting the number of packets present in the network to avoid an overloading of the resources, and PA1 the load balancing for fairly distributing the traffic over all the links of the network to avoid a local congestion in particular resources. PA1 Centralized Routing PA1 When the characteristics of the network fluctuate, it is possible to adapt the routing by assigning to one node the responsibility to update periodically the routing tables according to the traffic variations and the topology. This method, simple in its principles, is called Centralized Routing. Its principal disadvantage is to generate an important auxiliary traffic and to subordinate the good functioning of the network to only one node. Furthermore, the Centralized Routing can generate some problems at the time the tables are refreshed because said tables cannot be received at the same time by all the nodes. A solution is to decentralize the tables establishment at the level of each node. PA1 Distributed Routing PA1 The Distributed Routing is a method in which neighboring nodes are exchanging messages concerning the traffic and the network condition to update their own routing tables. PA1 1. Determining what the route for a given connection shall be, PA1 2. Actually switching the packet within a switching node. PA1 A connection request is specified by the user via a set of parameters including origin and destination address and data flow characteristics. PA1 The path determination is realized by the source node from its local routing Topology Database PA1 The route reservation is sent out in a special message along the specified nodes. Said message, which is usually routed according to the previously described Source Routing technique, signals the nodes to set up their connection tables and to reserve their resources to provide the level of service required by the traffic type (for example, a bandwidth reservation on each of the links of the path). PA1 The tables update reflects the changes in the availability of the network resources. The information is sent to every node in the network. PA1 The Reserved Communications for which the user is expecting from the network a committed bandwidth reserved and a guaranteed quality of service. PA1 The Non-Reserved Communications for which the expected service is "best effort delivery". Data are delivered as fast as possible when it is possible. PA1 weighing each transmission link with a weighing function w'.sub.ij dependent of both reserved and non-reserved traffic, so that: PA1 the higher the weight. PA1 determining the optimal route between the origin and the destination node by selecting links of lowest weights PA1 a Bounded Total Traffic Weight w.sub.BT,ij, PA1 an Excess Traffic Weight w.sub.E,ij, and PA1 a Reserved Traffic Weight w.sub.R,ij.
New Applications
On the other hand, in relation with these new emerging technologies, many potential applications that where not possible before are now becoming accessible and attractive. In this environment, three generic requirements are expressed by the users:
High Speed Packet Switching Networks
Data transmission is now evolving with a specific focus on applications and by integrating a fundamental shift in the customer traffic profile. Driven by the growth of workstations, the local area networks interconnection, the distributed processing between workstations and super computers, the new applications and the integration of various and often conflicting structures--hierarchical versus peer to peer, wide versus local area networks, voice versus data--the data profile has become more bandwidth consuming, bursting, non-deterministic and requires more connectivity. Based on the above, there is strong requirement for supporting distributed computing applications across high speed networks that can carry local area network communications, voice, video, and traffic among channel attached hosts, business, engineering workstations, terminals, and small to intermediate file servers. This vision of a high speed multiprotocol network is the driver for the emergence of fast packet switching networks architectures in which data, voice, and video information is digitally encoded, chopped into small packets and transmitted through a common set of nodes and links.
An efficient transport of mixed traffic streams on very high speed lines means for these new network architecture a set of requirements in term of performance and resource consumption which can be summarized as follows:
Connectivity
In high speed networks, the nodes must provide a total connectivity. This includes attachment of the user's devices, regardless of vendor or protocol, and the ability to have the end user communicate with any other device. The network must support any type of traffic including data, voice, video, fax, graphic or image. Nodes must be able to take advantage of all common carrier facilities and to be adaptable to a plurality of protocols. All needed conversions must be automatic and transparent to the end user.
Throughput and Processing Time
One of the key requirement of high speed packet switching networks is to reduce the end-to-end delay in order to satisfy real time delivery constraints and to achieve the necessary high nodal throughput for the transport of voice and video. Increases in link speeds have not been matched by proportionate increases in the processing speeds of communication nodes and the fundamental challenge for high speed networks is to minimize the packet processing time within each node. In order to minimize the processing time and to take full advantage of the high speed/low error rate technologies, most of the transport and control functions provided by the new high bandwidth network architectures are performed on an end-to-end basis. The flow control and particularly the path selection and bandwidth management processes are managed by the access points of the network which reduces both the awareness and the function of the intermediate nodes.
Flow and Congestion Control
Communication networks have at their disposal limited resources to ensure an efficient packets transmission. These limitations are principally located at the level of links bandwidth, nodes processing capacity and buffers size at the emission and reception of data packets. When the traffic demand increases, the network undergoes congestion phenomenons which take the form of a collapse of the network performances expressed in terms of actual throughput, average transfer delay of packets through the network, number of packets lost or in error . . . .
An ideal network should be able to transmit an useful traffic directly proportional to the traffic offered to the network and this as far as the maximum transmission capacity is reached. Beyond this limit, the network should operate at its maximum capacity whatever the demand is. In the reality, the operations diverge from the ideal for a certain number of reasons which are all related to the inefficient allocation of resources in overloaded environment. In particular, the size of the queues on the links increases rapidly in function of the traffic and exceeds the capacity of the buffers in the nodes. Packets which can not be stored any more are thrown away causing their retransmission and propagating congestion towards links located upstream generating an additional internal traffic. There is an avalanche phenomenon due to the fact that beyond a certain limit, the useful transport capacity of the network decreases when the demand for traffic increases.
For the operating to be satisfactory, the network must be implemented so as to avoid congestion. The simplest solution obviously consists in oversizing the equipments so as to be positioned in an operating zone which is distant from the congestion. This solution is generally not adopted for evident reasons of costs and it is necessary to apply a certain number of preventive measures among which the main ones are:
Bandwidth Management
An efficient bandwidth management is essential to take full advantage of a high speed network. While transmission costs per byte continue to drop year after year, transmission costs are likely to continue to represent the major expense of operating future telecommunication networks as the demand for bandwidth increases. Thus considerable efforts have been spent on designing flow and congestion control processes, and routing algorithms to better manage the network bandwidth.
Routing Modes
A general problem in the communication networks is to find a path between a source and a destination node. When the network is using datagrams, the path selection must be done individually for each packet. For virtual circuits, the path decision is done once only at the time of the connection (or session) establishment. In both cases, the choice of a routing algorithm is not easy because it must satisfy a large number of often conflicting requirements. This algorithm must be simple to implement for not complicating the nodes realization, it must ensure a correct progress of the packets whatever the disturbance on the network. The algorithm must be able to provide satisfying results despite of the traffic variations and the network topology. It must also ensure the equity between the different end users and provide an equal distribution of the rights to access the network. At last, the routing algorithm must allow, when possible, to exploit the network in an optimal way, according to a criterion which can vary with the utilization type. In most of the cases, the network is realized in a way to minimize the packet transit time and to transfer the maximum number of packets. In other cases, the objective is to decrease the communication cost, or to develop a reliable network able to operate correctly either in case of catastrophic line, node failure or peaks of traffic.
Because of the variety of the constraints, there are a large number of different routing types like Flooding Routing, Random or Stochastic Routing, Deterministic Routing. This last technique is one of the most widely used. Two modes of operation are opposed: the Fixed Routing and the Adaptive Routing.
Fixed Routing
The Fixed Routing defines paths that must take the different packets according to the general network characteristics such as the network topology and the mean traffic expected on the communication lines. The routing rules are established once and aims for optimizing the performance criterion privileged by the user. The Fixed Routing is very simple in its principles and allows to considerably speed up the packet transmission through the network. However, this technique is not very flexible.
Adaptive Routing
Contrary to the Fixed Routing, the purpose of the Adaptive Routing is to satisfy at any time the optimization criterion. Tables are permanently updated according to, for example, the instantaneous state of the traffic on the lines.
End-to-End Routing
The Distributed Routing is currently used in most high speed networks. Nodes are exchanging control messages to obtain all information required for routing packets. In order to minimize the processing time and to take full advantage of the high speed/low error rate technologies, the transport and control functions provided by the high bandwidth networks are performed on an end-to-end basis. No hop-by-hop error recovery or retransmission is envisioned in high speed, high performance (low error) links, and thus, there is no need for transit nodes to be aware of individual transport connections. The originating node is responsible for calculating the route that a packet must take through the network. The routing of the packets presents two aspects for which a wide range of implementing methods exists:
Connection-Oriented and Connectionless Routing
As described in the document High Speed Networking Technology, An Introductory Survey (pages 116 to 129)--GG24-3816-00 ITSC Raleigh June 1993, one distinguishing characteristic of a network is the presence or absence of a "connection" between end users. They are many ways of constructing connectionless or connection-oriented networks. In most of cases, packets using different routing modes can share the same data transmission facilities. Two routing modes are widely used and are described as example: the Automatic Network Routing and the Label Swapping.
Automatic Network Routing
The Automatic Network Routing is a particular implementation of the Distributed Routing for connectionless networks. The source node (or access node) is responsible for calculating the route the packet must take through the network. Each packet includes in its routing field a list of labels of all links through which the packet will pass as it move across the network. The labels are used by the intermediate nodes to direct the packet towards its destination. Each packet is routed through the network as a self contained unit and is independent of all other packets. Automatic Network Routing requires no connection set up activity in intermediate nodes and support true datagram services.
Label Swapping
The Label Swapping is a particular implementation of the Distributed Routing for connection oriented networks. These networks typically multiplex many connections (or sessions) on a link using some form of logical "channel". Each packet sent on the link has a header which includes an arbitrary number identifying which logical connection that this packet belongs to. The call set up and the resource reservation process comprises the following steps:
The Label Swapping technique requires that the connection tables be set up and maintained dynamically in each node. This restriction makes datagram transport quite inefficient. However, due to the low packet overhead, this technique is particularly adapted to the transmission of very short packets (for example real-time voice connections).
Reserved and Non-Reserved Traffic
On large Networks with disparate traffic, two types of communications can be defined:
While the connectionless routing modes are quite efficient to route packets that does not require any reservation nor quality of service, connection oriented routing is well adapted to route packets when bandwidth reservation and quality of service are expected to be provided. In other words, connectionless routing suits non-reserved traffic requirements while connection oriented routing suits reserved traffic better. For this reason, it looks difficult to mix these two types of traffic, reserved and non-reserved, in a single connection oriented network. The problem to solve is the fairness between the two. Non-reserved traffic is important and must be transmitted with reasonable delay and quality (loss, corruption, . . . ): this is the interest of the user. But this is also this interest of the network. Most of the time, when facing a delay or quality problem, users with non-reserved traffic try to retransmit the data and therefore overload the network. The set up of reserved connections does not need to take into account non-reserved traffic, because, by definition, reserved traffic takes always priority over non-reserved traffic. The problem of fairness is then the problem of finding a path for the non-reserved traffic taking advantage of bandwidth holes.